package com.kiwi.nixu;

import com.kiwi.nixu.common.LNode;
import com.sun.org.apache.bcel.internal.generic.NEW;

import java.net.InetAddress;
import java.util.List;

/**
 * @Author: zqb
 * @Description: 如何实现链表逆序
 * m1:就地逆序
 * m2:递归法
 * m3:插入法，效率最大高
 * @Date: Created in 17:18 2020/1/22
 * @Create By:
 */
public class TestNiXuLinkedList {


    public static void main(String[] args) {

    }


    /**
     * 思路：【重点在于有一个哨兵节点，就是一个head节点】从链表的第二个结点开始，
     * 把遍历到的结点插入到头结点的后面，直到遍历结束。假定原链表为head→1→2→3→4→5→6→7，
     * 在遍历到2时，将其插入到头结点后，链表变为head→2→1→3→4→5→6→7，
     * 同理将后序遍历到的所有结点都插入到头结点head后，就可以实现链表的逆序。实现代码如下：
     *
     * @param head
     */
    public static void reverse(LNode head) {

        if (head != null || head.next != null) {
            return;
        }
        LNode cur = null;//当前节点
        LNode next = null;//后继节点
        //设置除了第一个节点的下一个节点为当前节点（必须说明这个链表有一个head节点为哨兵节点，就是data不存数据）
        cur = head.next.next;
        //设置链表第一个节点为尾巴结点
        head.next.next = null;

        // x>1>2>3>4>5
        //遍历节点
        //cur=2
        while (cur != null) {
            //得到当前节点的下一个节点，即下一次要遍历的节点

            //3
            next = cur.next;

            //b:x>1>2>3>4>5
            //a:x>1>2>1>2...
            cur.next = head.next;//2>1

            head.next = cur;

            //b:x>2>1>2>1...
            //a:x>2>1>2>1...
            cur = next;
        }
    }
}
